package com.sunny;

import java.util.Arrays;
import java.util.List;

public class Main {

    public static void main(String[] args) {

        List<Integer> post = Arrays.asList(4,8,5,2,9,6,7,3,1);
        List<Integer> in = Arrays.asList(4,2,8,5,1,9,6,3,7);

        Node root = getTree(post, 8, in, 0, 8);

        preOrder(root);
    }

    public static void preOrder(Node node){

        System.out.print(node.getValue() + " ");
        if(null != node.getLeft())
            preOrder(node.getLeft());
        if(null != node.getRight())
            preOrder(node.getRight());

    }

    public static Node getTree(List<Integer> post, int ind, List<Integer> in, int s, int t){
        if(s > t)
            return null;
        if(s == t){
            return new Node(in.get(s));
        }

        int val = post.get(ind);
        Node node = new Node(val);
        int mid = getMid(in, s, t, val);
        node.setLeft(getTree(post, ind-(t-mid+1), in, s, mid-1));
        node.setRight(getTree(post, ind-1, in, mid+1, t));
        return node;

    }

    public static int getMid(List<Integer> in, int s, int t, int val){

        int res = 0;
        for (int i=s;i<=t;i++){

            if(val == in.get(i)){
                res = i;
                break;
            }

        }
        return res;

    }

}

class Node{

    int value;
    Node left,right;

    public Node() {
    }

    public Node(int value) {
        this.value = value;
    }

    public Node(int value, Node left, Node right) {
        this.value = value;
        this.left = left;
        this.right = right;
    }

    public int getValue() {
        return value;
    }

    public void setValue(int value) {
        this.value = value;
    }

    public Node getLeft() {
        return left;
    }

    public void setLeft(Node left) {
        this.left = left;
    }

    public Node getRight() {
        return right;
    }

    public void setRight(Node right) {
        this.right = right;
    }
}
